package day_2022_7_to_8.day48;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/08/19 12:09
 **/
public class Day34_2_Num68_FullJustify {
    class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            List<String> res = new ArrayList<>();
            int left = 0;
            int right = 0;
            while(right < words.length) {
                left = right;
                int sumLen = words[left].length();
                right++;
                while(right < words.length && sumLen + words[right].length() + 1 <= maxWidth) {
                    sumLen += words[right].length() + 1;
                    right++;
                }
                //如果到达最后一个单词 或 该行只有一个单词
                if(right == words.length || left == right - 1) {
                    String temp = join(words, left, right - 1, " ") + blank(maxWidth - sumLen);
                    res.add(temp);
                    continue;
                }
                int wordsNum = right - left;
                int wordsLen = sumLen - (wordsNum - 1);
                int averageSpace = (maxWidth - wordsLen) / (wordsNum - 1);
                int extraSpace = (maxWidth - wordsLen) % (wordsNum - 1);
                String temp = join(words, left, left + extraSpace, blank(averageSpace + 1));
                temp += blank(averageSpace);
                temp += join(words, left + extraSpace + 1, right - 1, blank(averageSpace));
                res.add(temp);
            }
            return res;
        }
        public String join(String[] words, int left, int right, String s) {
            StringBuilder res = new StringBuilder(words[left]);
            for(int i = left + 1; i <= right; i++) {
                res.append(s + words[i]);
            }
            return res.toString();
        }
        public String blank(int n) {
            String res = "";
            for(int i = 0; i < n; i++) {
                res += " ";
            }
            return res;
        }
    }
}